МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національний університет “Львівська політехніка”
Методи умовної оптимізації МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” ЗАТВЕРДЖЕНО На засіданні кафедри САПР Протокол № 1 від 28.08.2008 р. ЛЬВІВ 2008 Методи умовної оптимізації. Методичні вказівки до лабораторної роботи № 6 з курсу “Методи синтезу та оптимізації” для студентів базового напряму 6.08.04 “Компютерні науки” /Укл. Теслюк В. М., Андрійчук М. І. – Львів: НУ “ЛП”, 2008 р. Укладачі: Теслюк Василь Миколайович, к.т. н., доцент; Андрійчук Михайло Іванович, к. ф.-м. н., доцент. Відповідальний за випуск: Ткаченко С. П., к.т. н., доцент. Рецензенти: Каркульовський В. І., к.т. н., доцент, Стех Ю. В., к.т. н., доцент. 1. МЕТА РОБОТИ Навчитися використовувати методи умовної оптимізації при знаходженні екстремумів функцій багатьох змінних з обмеженнями 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Критерії оптимальності в задачах з обмеженнями У методичних вказівках до лабораторної роботи № 4 було розглянуто необхідні і достатні умови оптимальності рішень оптимизаційних задач без обмежень. Однак ряд інженерних задач пов'язаний з оптимізацією при наявності деякої кількості обмежень на керовані змінні. Такі обмеження істотно зменшують розміри області, у якій проводиться пошук оптимуму. На перший погляд може здаатися, що зменшення розмірів доустимої області повинне спростити процедуру пошуку оптимуму. Тим часом, навпаки, процес оптимізації стає більш складним, оскільки установлені вище критерії оптимальності не можна використовувати при наявності обмежень. При цьому може порушуватися навіть основна умова, відповідно до якого оптимум повинний досягатися в стаціонарній точці, що характеризується нульовим градієнтом. Наприклад, безумовний мінімум функції f(x)=(x—2)2 має місце в стаціонарній точці х=2. Але якщо задача мінімізації розв’язується з урахуванням обмеження х>4, то буде знайдений умовний мінімум, якому відповідає точка х=4. Ця точка не є стаціонарною точкою функції f, тому що f’(4)=4. Нижче досліджуються необхідні і достатні умови оптимальності рішень задач з обмеженнями. Виклад починається з розгляду, задач оптимізації, що містять тільки обмеження у виді рівностей. Задачі з обмеженнями у виді рівностей Розглянемо загальну задачу оптимізації, що містить декілька обмежень у виді рівностей: мінімізувати
при обмеженнях .
. (1) Ця задача в принципі може бути вирішена як задача безумовної оптимізації, отримана шляхом виключення з цільової функції
незалежних змінних за допомогою заданих рівностей. Наявність обмежень у виді рівностей фактично дозволяє зменшити розмірність вихідної задачі з N до N-K. Оскільки при цьому виникає задача безумовної оптимізації, то для ідентифікації точки оптимуму можна використовувати методи для оптимізації без обмежень. Як ілюстрацію, розглянемо наступний приклад. Приклад 1. Мінімізувати
при обмеженні
. Виключивши змінну x3 за допомогою рівняння
, одержимо оптимізаційну задачу з двома змінними без обмежень
. Для ідентифікації точки оптимуму досліджуваної функції можна використовувати один з методів безумовної мінімізації. Метод виключення змінних можна застосувати лише в тих випадках, коли рівняння, що представляють обмеження, можна розв’язати щодо деякого конкретного набору незалежних змінних. При наявності великого числа обмежень у виді рівностей процес виключення змінних стає дуже трудомісткою процедурою. Крім того, можливі ситуації, коли рівняння не вдається розв’язати щодо змінної. Зокрема, якщо в Прикладі 1 обмеження
задати у виді
, то одержати аналітичнийе вираз якої-небудь зі змінних через інші неможливо. Таким чином, при рішенні задач, що містять складні обмеження у виді рівностей, доцільно використовувати метод множників Лагранжа, опис якого дається в наступному розділі. Множники Лагранжа За допомогою методу множників Лагранжа власне кажучи встановлюються необхідні умови, що д...